package list

// 递归版本
func MergeTwoList(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}

	if list1.Val < list2.Val {
		list1.Next = MergeTwoList(list1.Next, list2)
		return list1
	}
	list2.Next = MergeTwoList(list1, list2.Next)
	return list2
}

// 迭代版本
func MergeTwoList2(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}

	dummyHead := &ListNode{
		Val:  -1,
		Next: nil,
	}
	temp := dummyHead
	for list1 != nil && list2 != nil {
		if list1.Val < list2.Val {
			temp.Next = list1
			list1 = list1.Next
		} else {
			temp.Next = list2
			list2 = list2.Next
		}
		temp = temp.Next
	}

	if list1 != nil {
		temp.Next = list1
	}
	if list2 != nil {
		temp.Next = list2
	}

	return dummyHead.Next
}
